package chapter_2.merge;

import java.util.Arrays;

/**
 * (MergeSortNoSentinel).
 *
 * @author 汪文波(Wang Wenbo) wenboit@163.com
 * @notes Create on 2021-12-04 20:36
 */
public class MergeSortNoSentinel {

    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3};
        //int[] arr = {5, 2};
        MergeSortNoSentinel.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        MergeSortNoSentinel.sort(arr, 0, arr.length);
    }

    public static void sort(int[] arr, int p, int r) {
        if (p < r - 1) {
            int q = p + (r - p) / 2;
            MergeSortNoSentinel.sort(arr, p, q);
            MergeSortNoSentinel.sort(arr, q, r);
            MergeSortNoSentinel.merge(arr, p, q, r);
        }
    }

    public static void merge(int[] arr, int p, int q, int r) {
        // 左右子数组
        int n1 = q - p;
        int n2 = r - q;
        int[] left = new int[n1];
        int[] right = new int[n2];
        for (int i = 0; i < n1; i++) {
            left[i] = arr[p + i];
        }
        for (int i = 0; i < n2; i++) {
            right[i] = arr[q + i];
        }
        // 左右子数组比较
        int i = 0, j = 0;
        int k = p;
        while (i < n1 && j < n2) {
            if (left[i] < right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }
        // 复制剩余子数组
        if (i == n1){
            for (;k < r; k++){
                arr[k] = right[j];
                j++;
            }
        }
        if (j == n2){
            for (;k < r; k++){
                arr[k] = left[i];
                i++;
            }
        }
    }

}
